package com.dh.leetcode.four;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassName: _424_Minimum_number_of_arrows_to_burst_balloons
 * @Description: 452. 用最少数量的箭引爆气球
 * <p>
 * https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
 * 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，
 * 因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
 * <p>
 * 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
 * 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。
 * 我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
 * <p>
 * 给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
 * @Author: shouzimu
 * @Date: 2020/11/23 10:00
 */
public class _452_Minimum_number_of_arrows_to_burst_balloons {


    /**
     * 从提交的题解看，使用结束位置排序效果更好，不过没有进行编码和测试
     * <p>
     * <p>
     * 1、按起始位置排序
     * 2、找到边界，第一个不在范围内的情况下 箭数量+1
     * <p>
     * 看了大佬们的解法，按照坐标结束排序性能更好，复杂度为O(N)
     *
     * @param points
     * @return
     */
    public int findMinArrowShots(int[][] points) {
        int len = points.length;
        if (len == 0) {
            return 0;
        }
        Arrays.sort(points, Comparator.comparingInt(t -> t[0]));
        int num = 1;
        int i = 0;
        int minEnd = Integer.MAX_VALUE;
        while (i < len - 1) {
            minEnd = Math.min(minEnd, points[i][1]);
            boolean add = false;
            for (int j = i + 1; j < len; j++) {
                int end = points[j][1];
                int start = points[j][0];
                if (end < minEnd) {
                    minEnd = end;
                }
                if (start > minEnd) {
                    num++;
                    i = j;
                    add = true;
                    minEnd = Integer.MAX_VALUE;
                    break;
                }
            }
            if (!add) {
                i++;
            }
        }
        return num;
    }

    @Test
    public void findMinArrowShotsTest() {
        int[][] points = new int[][]{{0, 9}, {1, 8}, {7, 8}, {1, 6}, {9, 16}, {7, 13}, {7, 10}, {6, 11}, {6, 9}, {9, 13}};
        Assert.assertEquals(3, findMinArrowShots(points));

        points = new int[][]{{1, 2}, {3, 4}, {5, 6}, {7, 8}};
        Assert.assertEquals(4, findMinArrowShots(points));

        points = new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        Assert.assertEquals(2, findMinArrowShots(points));

        points = new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}};
        Assert.assertEquals(2, findMinArrowShots(points));
    }


}
